home *** CD-ROM | disk | FTP | other *** search
/ Tricks of the Mac Game Programming Gurus / TricksOfTheMacGameProgrammingGurus.iso / More Source / Libraries / VideoToolbox 95.04.18 / VideoToolboxSources / Normal.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-25  |  7.7 KB  |  246 lines  |  [TEXT/MMCC]
  1. /*
  2. Normal.c
  3. statistical functions related to the normal distribution.
  4. Also see: Binomial.c,ChiSquare.c, Exponential.c, Uniform.c
  5.  
  6.     f=NormalPdf(x);
  7.     p=Normal(x);
  8.     x=InverseNormal(p);
  9.     x=NormalSample();
  10.     f=Normal2DPdf(double r);
  11.     p=Normal2D(r);
  12.     r=InverseNormal2D(p);
  13.     r=Normal2DSample();
  14. Normal2D is a Gaussian pdf over two dimensions, integrated over all orientations,
  15. 0 to 2π. r is the distance from the origin, [0,Inf]. 
  16.  
  17.     BoundedNormalIntegers(distribution,n,mean,sd,min,max);
  18. Fills the "distribution" array with n ordered integers so that random samples
  19. from the array,
  20.     i=distribution[nrand(n)];
  21. will have, as nearly as possible, the specified distribution, i.e. they will
  22. be samples (rounded to integer) drawn from the interval [min-.5,max+.5],
  23. where min and max are integers, of a normal distribution with the specified
  24. mean and variance. Specifying an infinite sd will result in a uniform
  25. distribution over the interval [min,max]. (This is detected as a special
  26. case and performed quickly.) Once the distribution array has been filled,
  27. random samples from it are a fast way of generating bounded Gaussian noise
  28. to be added to each pixel of an image. Note that "mean" and "sd" apply only
  29. to the unclipped underlying normal distribution. Call this
  30.     mean=MeanW(distribution,n,&sd);
  31. to compute the mean and sd of your integer distribution. The runtime of 
  32. BoundedNormalIntegers will be proportional to max-min+1, and nearly independent
  33. of n. It takes about 0.3 s on a Mac IIci for max-min+1=256.
  34.  
  35. Copyright (c) 1989,1990,1991,1992,1995 Denis G. Pelli
  36. HISTORY:
  37. 1989    dgp wrote it.
  38. 4/8/90    dgp    changed the names of the routines. 
  39.             Made sure that domain error produces NAN.
  40. 6/90    dgp    added NormalSample()
  41. 7/30/91    dgp    now use NAN defined in VideoToolbox.h
  42. 12/28/91 dgp sped up NormalPdf() by calculating the scale factor only once
  43. 12/29/91 dgp extracted code to create new routine UniformSample.c
  44. 1/11/92    dgp    rewrote Normal()'s polynomial evaluation to halve the number of multiplies
  45.             Renamed NormalPDF() to NormalPdf().
  46. 1/19/92    dgp    defined the constants LOG2 and LOGPI in VideoToolbox.h
  47.             Added more domain tests, returning NAN if outside. 
  48.             Added more checks to main().
  49.             Wrote Normal2DPdf(),Normal2D(),InverseNormal2D(),and Normal2DSample().
  50. 2/1/92    dgp    Redefined Normal2DPdf(r) to now, more sensibly, treat r as the random
  51.             variable, rather than the implicit x and y, where r=sqrt(x^2+y^2). 
  52.             Previously, Normal2D(R)=Integrate[2 Pi r Normal2DPdf(r),{r,0,R}]
  53.             now Normal2D(R)=Integrate[Normal2DPdf(r),{r,0,R}]. There is no change
  54.             in Normal2D(). I suspect that Normal2D is in fact the Raleigh distribution,
  55.             and I will rename it if this is in fact the case.
  56. 11/13/92 dgp InverseNormal(0) now returns -INF, and InverseNormal(1) returns INF.
  57. 12/15/93 dgp declared some arguments "register".
  58. 3/26/94    dgp    added BoundedNormalIntegers().
  59.             Asked compiler to use 68881 instructions for transcendentals.
  60. */
  61. #include "VideoToolbox.h"
  62. #include <assert.h>
  63. #include <math.h>
  64. #include "mc68881.h"
  65. void BoundedNormalIntegers(short *distribution,long n,double mean,double sd
  66.     ,short min,short max);
  67. #if THINK_C && mc68881
  68.     #define exp _exp    /* use fast 68881 instruction instead of SANE */
  69.     #define log _log    /* use fast 68881 instruction instead of SANE */
  70.     #define sqrt _sqrt    /* use fast 68881 instruction instead of SANE */
  71. #endif
  72.  
  73. double NormalPdf(register double x)
  74. /* Gaussian pdf. Zero mean and unit variance. */
  75. {
  76.     if(IsNan(x))return x;
  77.     return exp(-0.5*(x*x+(LOG2+LOGPI)));
  78. }
  79.  
  80. double Normal(register double x)
  81. /*
  82. Cumulative normal distribution. From Abramowitz and Stegun Eq. (26.2.17).
  83. Error |e|<7.5 10^-8
  84. */
  85. {
  86.     register double P,t;
  87.     
  88.     if(x<0.0) return 1.0-Normal(-x);
  89.     t=1.0/(1.0+0.2316419*x);
  90.     P=(0.319381530+(-0.356563782+(1.781477937+(-1.821255978+1.330274429*t)*t)*t)*t)*t;
  91.     return 1.0-NormalPdf(x)*P;
  92. }
  93.  
  94. double InverseNormal(register double p)
  95. /*
  96. Inverse of Normal(), based on Abramowitz and Stegun Eq. 26.2.23.
  97. Error |e|<4.5 10^-4.
  98. */
  99. {
  100.     register double t,x;
  101.     
  102.     if(IsNan(p))return p;
  103.     if(p<0.0)return NAN;
  104.     if(p==0.0)return -INF;
  105.     if(p>0.5) return -InverseNormal(1.0-p);
  106.     t=sqrt(-2.0*log(p));
  107.     x=t-(2.515517+(0.802853+0.010328*t)*t)/(1.0+(1.432788+(0.189269+0.001308*t)*t)*t);
  108.     return -x;
  109. }
  110.  
  111. double NormalSample(void)
  112. {
  113.     return InverseNormal(UniformSample());
  114. }
  115.  
  116. double Normal2DPdf(double r)
  117. /* Gaussian pdf over two dimensions, integrated over all orientations, 0 to 2π. */
  118. /* The argument is taken to be the distance from the origin, [0,Inf]. */
  119. /* The rms is 1 */
  120. {
  121.     if(IsNan(r))return r;
  122.     if(r<=0.0)return 0.0;
  123.     return 2*r*exp(-r*r);
  124. }
  125.  
  126. double Normal2D(double r)
  127. /* Integral of Normal2DPdf() from zero to r. */
  128. {
  129.     if(IsNan(r))return r;
  130.     if(r<=0.0)return 0.0;
  131.     return 1.0-exp(-r*r);
  132. }
  133.  
  134. double InverseNormal2D(double p)
  135. {
  136.     if(IsNan(p))return p;
  137.     if(p<0.0 || p>1.0)return NAN;
  138.     return sqrt(-log(1.0-p));
  139. }
  140.  
  141. double Normal2DSample(void)
  142. /* rms is 1 */
  143. {
  144.     return InverseNormal2D(UniformSample());
  145. }
  146.  
  147. /*
  148.     Integrate[exp(-.5*u^2),{u,a,a+1/sd}]
  149.     =exp(-.5*a^2)*Integrate[exp(-.5*((a+e)^2-a^2)),{e,0,1/sd}]
  150.     =exp(-.5*a^2)*Integrate[exp(-.5*e*e)*exp(-a*e),{e,0,1/sd}]
  151.     =exp(-.5*a^2)*Integrate[(1-.5*e*e)*exp(-a*e),{e,0,1/sd}]
  152.     =exp(-.5*a^2)*((exp(-a/sd) - 1)/(-a)-.5*Integrate[e*e*exp(-a*e),{e,0,1/sd}])
  153.     =exp(-.5*a^2)*(1-exp(-a/sd))/a
  154. */
  155. void BoundedNormalIntegers(register short *distribution,long n,double mean,double sd
  156.     ,short min,short max)
  157. {
  158.     register short i;
  159.     register long j,count,values,round;
  160.     double p,p0,p1,x;
  161.     short shortcut;
  162.     
  163.     j=0;
  164.     if(IsInf(sd)){
  165.         // Uniform distribution over the interval [min,max]
  166.         values=max-min+1;
  167.         assert(n<LONG_MAX/values);
  168.         round=values/2;
  169.         for(i=min;i<max;i++){
  170.             count=((i-min+1)*n+round)/values;
  171.             while(j<count)distribution[j++]=i;
  172.         }
  173.     }else{    
  174.         shortcut=sd*sd>n;    // guarantees count will err by at most ±0.5
  175.         p=p0=Normal((min-.5-mean)/sd);
  176.         p1=Normal((max+.5-mean)/sd)-p0;
  177.         for(i=min;i<max;i++){
  178.             x=(i+.5-mean)/sd;
  179.             if(shortcut)p+=NormalPdf(x)*(exp(x/sd)-1)/x;
  180.             else p=Normal(x);
  181.             count=0.5+n*(p-p0)/p1;
  182.             while(j<count)distribution[j++]=i;
  183.         }
  184.     }
  185.     while(j<n)distribution[j++]=max;
  186. }
  187.  
  188.  
  189. #if 0 /* A test program. */
  190.     void main()
  191.     {
  192.         double x,y,sum,dx,a,b,mean,sd;
  193.         static double z[1000];
  194.         int i;
  195.         
  196.         Require(0);
  197.         srand(clock());
  198.         printf("%4s%15s%15s%20s%15s\n","x","NormalPdf(x)","Normal(x)","InverseNormal","Error");
  199.         for(x=-4.0;x<=4.0;x+=2.0){
  200.             printf("%4.1f%15.8f%15.8f%20.4f%15.4f\n",
  201.             x,NormalPdf(x),Normal(x),InverseNormal(Normal(x)),InverseNormal(Normal(x))-x);
  202.         }
  203.         sum=0.0;
  204.         dx=0.001;
  205.         for(x=-1.;x<0.;x+=dx)sum+=NormalPdf(x);
  206.         sum*=dx;
  207.         sum-=Normal(0.0)-Normal(-1.0);
  208.         printf("Partial integral of NormalPdf error %.5f\n",sum);
  209.         for(i=0;i<1000;i++)z[i]=NormalSample();
  210.         mean=Mean(z,1000,&sd);
  211.         printf("1000 samples mean %.2f sd %.2f\n",mean,sd);
  212.         printf("\n");
  213.     
  214.         printf("%4s%15s%15s%20s%15s\n","x","Normal2DPdf(x)","Normal2D(x)","InverseNormal2D","Error");
  215.         for(x=-1.;x<=5.0;x+=1.0){
  216.             printf("%4.1f%15.8f%15.8f%20.4f%15.4f\n",
  217.             x,Normal2DPdf(x),Normal2D(x),InverseNormal2D(Normal2D(x)),InverseNormal2D(Normal2D(x))-x);
  218.         }
  219.         sum=0.0;
  220.         dx=0.0001;
  221.         for(x=0;x<1.;x+=dx)sum+=Normal2DPdf(x);
  222.         sum*=dx;
  223.         sum-=Normal2D(1.0);
  224.         printf("Partial integral of Normal2DPdf error %.5f\n",sum);
  225.         for(i=0;i<1000;i++)z[i]=Normal2DSample();
  226.         mean=Mean(z,1000,&sd);
  227.         printf("1000 samples rms %.2f\n",sqrt(mean*mean+sd*sd));
  228.         printf("\n");
  229.         for(i=0;i<1000;i++){
  230.             x=NormalSample();
  231.             y=NormalSample();
  232.             z[i]=sqrt((x*x+y*y)/2.);
  233.         }
  234.         mean=Mean(z,1000,&sd);
  235.         printf("1000 (x,y) normal samples with sd 2^-0.5 have rms hypotenuse of %.2f\n",sqrt(mean*mean+sd*sd));
  236.         printf("\n");
  237.     
  238.         a=4.0*atan(1.0);
  239.         if(a!=PI)printf("4*atan(1)-PI %.19f\n",a-PI);
  240.         a=log(a);
  241.         if(a!=LOGPI)printf("Error: log(PI) %.19f, error in LOGPI %.19f\n",a,LOGPI-a);
  242.         a=log(2.0);
  243.         if(a!=LOG2)printf("Error: log(2) %.19f, error in LOG2 %.19f\n",a,LOG2-a);
  244.     }
  245. #endif
  246.